#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    auto dfs = [&](auto&& dfs, int u, int tot, vector<int>& st) {
        if (u == candidates.size())  return;
        if (tot == 0)
        {
            res.push_back(st);
            return;
        }
        dfs(dfs, u + 1, tot, st);
        if (tot - candidates[u] >= 0)
        {
            st.push_back(candidates[u]);
            dfs(dfs, u, tot - candidates[u], st);
            st.pop_back();
        }
    };

    vector<int> st;
    dfs(dfs, 0, target, st);
    return res;
}